// hard

// 给定一个整数数组nums和一个整数k，找出nums中和至少为k的最短非空子数组，并返回该子数组的长度，如果不存在这样的子数组，返回-1
// 子数组是数组中连续的一部分

function shortestSubarray(nums, k) {
    // 前缀和
    const sum = [0]
    for (let i = 0; i < nums.length; i++) {
        sum[i + 1] = sum[i] + nums[i]
    }

    // 前缀和单调递增队列
    const queue = [0]
    let pos = -1, ans = Number.MAX_SAFE_INTEGER
    for (let i = 0; i < sum.length; i++) {
        // 固定末尾，往前寻找符合要求的最短子数组
        // sum[i] - sum[queue[0]] 和最大的位置
        while (queue.length && sum[i] - sum[queue[0]] >= k) {
            pos = queue.shift()
        }
        if (pos !== -1 && (i - pos < ans || ans === Number.MAX_SAFE_INTEGER)) {
            ans = i - pos
        }
        // 维护单调递增队列的单调性
        while (queue.length && sum[queue[queue.length - 1]] > sum[i]) {
            queue.pop()
        }
        queue.push(i)
    }
    return ans === Number.MAX_SAFE_INTEGER ? -1 : ans
}

let nums = [2, -1, 2], k = 3
console.log(shortestSubarray(nums, k));